package com.lfg.leetcode.leetcode1500;


import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Comparator;

public class No1620BestCoordinate {
    public static void main(String[] args) {
        int[][] properties1 = {{32, 36, 27}, {17, 22, 43}, {8, 11, 41}, {46, 28, 7}, {22, 4, 35}, {41, 8, 33}, {32, 29, 4}, {44, 32, 16}, {33, 20, 16}, {3, 38, 35}, {17, 47, 23}, {33, 0, 29}, {29, 19, 6}, {4, 50, 46}, {19, 47, 6}, {48, 6, 41}, {20, 26, 35}};
        int[][] properties = {{36, 33, 42}, {30, 1, 49}, {16, 14, 2}, {29, 8, 0}, {5, 5, 22}, {15, 14, 31}, {15, 32, 12}, {6, 17, 31}, {1, 38, 18}, {49, 48, 18}, {49, 15, 0}, {32, 23, 32}, {50, 32, 28}, {33, 12, 30}, {28, 30, 44}, {5, 27, 38}, {5, 6, 32}, {22, 49, 17}, {40, 37, 28}};
        System.out.println(JSON.toJSONString(bestCoordinate(properties, 49)));
    }


    public static int[] bestCoordinate(int[][] towers, int radius) {
        Arrays.sort(towers, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
            }
        });
        int[] ret = new int[2];
        int left = 0;
        int right = 0;
        int top = 0;
        int end = 0;
        for (int[] p : towers) {
            left = Math.min(left, p[0]);
            right = Math.max(right, p[0]);
            end = Math.min(end, p[1]);
            top = Math.max(top, p[1]);
        }
        int maxRadius = 0;

        int[][] matrix = new int[right + 1][top + 1];

        for (int[] p : towers) {
            int xEnd = Math.min(right, p[0] + p[2]);
            for (int i = Math.max(p[0] - p[2], left); i <= xEnd; i++) {
                for (int j = Math.max(p[1] - p[2], end); j <= Math.min(p[1] + p[2], top); j++) {
                    double sqrt = getSqrt(p[0] - i, p[1] - j);
                    if (sqrt > radius) {
                        continue;
                    }
                    double floor = Math.floor(p[2] / (1 + sqrt));
                    matrix[i][j] += floor;
                    if (matrix[i][j] == maxRadius) {
                        if (ret[0] > i || (ret[0] == i && ret[1] > j)) {
                            maxRadius = matrix[i][j];
                            ret = new int[]{i, j};
                        }
                    } else if (matrix[i][j] > maxRadius) {
                        maxRadius = matrix[i][j];
                        ret = new int[]{i, j};
                    }
                }
            }
        }
        return ret;
    }

    private static double getSqrt(Integer x, Integer y) {
        return Math.sqrt(x * x + y * y);
    }


    public static int[] bestCoordinate2(int[][] towers, int radius) {
        int[] result = new int[2];//结果
        int maxRadius = 0;//该结果的信号合计
        int top = towers[0][1];//边界值
        int end = towers[0][1];
        int left = towers[0][0];
        int right = towers[0][0];
        //计算边界值
        for (int[] temp : towers) {
            top = top < temp[1] ? temp[1] : top;
            end = end > temp[1] ? temp[1] : end;
            left = left > temp[0] ? temp[0] : left;
            right = right < temp[0] ? temp[0] : right;
        }
        //逐格计算信号值，找到最大信号点
        for (int x = left; x <= right; x++) {
            for (int y = end; y <= top; y++) {
                int Totalradius = 0;
                if (x == 17 && y == 22) {
                    System.out.println(" floor=");
                }
                for (int[] temp : towers) {
                    if (sqrt(x, y, temp[0], temp[1]) <= radius) {
                        Totalradius += Math.floor(temp[2] / (1 + sqrt(x, y, temp[0], temp[1])));
                    }
                }
                if (Totalradius > maxRadius) {
                    maxRadius = Totalradius;
                    result[0] = x;
                    result[1] = y;
                }
            }
        }
        return result;
    }

    //很偷懒的计算距离函数
    public static double sqrt(int x, int y, int a, int b) {
        return Math.sqrt((a - x) * (a - x) + (b - y) * (b - y));
    }

}

